package com.fanshuai.graph;

import com.fanshuai.queue.LinkedQueue;
import com.fanshuai.queue.Queue;
import com.fanshuai.stack.LinkedStack;
import com.fanshuai.stack.Stack;
import com.fanshuai.tree.Visitor;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph implements IGraph {
    /**
     * 最大节点数量
     */

    private int initNodeSize = 100;
    private int maxNodeSize = 10000;

    /**
     * 节点
     */
    private Vertex[] nodes;
    /**
     * 邻接矩阵
     */
    private int[][] matrix;

    /**
     * 节点数量和当前节点容量
     */
    private int nodeNum = 0;
    private int capacity = 100;

    public Graph() {
        nodes = new Vertex[initNodeSize];
        matrix = new int[initNodeSize][initNodeSize];
        nodeNum = 0;
        capacity = initNodeSize;
    }

    private int calcNodeCapacity() throws Exception {
        int capacity = 0;
        if (2 * this.capacity <= 1000) {
            capacity = 2 * this.capacity;
        } else {
            capacity = this.capacity + 1000;
        }

        if (capacity > maxNodeSize) {
            throw new Exception("node num greater than 10000");
        }

        return capacity;
    }

    /**
     * 扩充图
     * @throws Exception
     */
    private void resize() throws Exception {
         int capacity = calcNodeCapacity();
         this.capacity = capacity;

         Vertex[] newNodes = new Vertex[capacity];
         System.arraycopy(nodes, 0, newNodes, 0, nodeNum);
         nodes = newNodes;

         int[][] newMatrix = new int[capacity][capacity];
         for (int i = 0; i < nodeNum; i++) {
             System.arraycopy(matrix[i], 0, newMatrix[i], 0, nodeNum);
         }
         matrix = newMatrix;
    }

    /**
     * 添加节点
     * @param value
     */
    public void addNode(int value) throws Exception {
        if ((nodeNum + 1) > capacity) {
            resize();
        }
        nodes[nodeNum] = new Vertex(value);
        nodeNum++;
    }

    /**
     * 添加边
     * @param start
     * @param end
     */
    public void addEdge(int start, int end) throws Exception {
        if (start < 0 || start >= nodeNum) {
            throw new Exception("edge start out of bound, start=" + start);
        }
        if (end < 0 || end >= nodeNum) {
            throw new Exception("edge end out of bound, end=" + end);
        }

        matrix[start][end] = 1;
        matrix[end][start] = 1;
    }

    /**
     * 深度优先搜索  递归算法
     * @param visitor
     */
    @Override
    public void dfsReverse(Visitor visitor) {
        if (nodeNum == 0) {
            return;
        }

        Map<Integer, Boolean> visitedMap = new HashMap<>();
        dfsReverse(visitor, visitedMap, 0);
    }

    private boolean isVisited(Map<Integer, Boolean> visitedMap, int nodeIndex) {
        Boolean b = visitedMap.get(nodeIndex);
        return b != null && b;
    }

    /**
     * 深度优先搜索  递归算法
     * @param visitor
     * @param visitedMap
     * @param nodeIndex
     */
    private void dfsReverse(Visitor visitor, Map<Integer, Boolean> visitedMap, int nodeIndex) {
        int value = nodes[nodeIndex].value;
        visitor.visit(value);
        visitedMap.put(nodeIndex, true);

        for (int j = 0; j < nodeNum; j++) {
            //节点有连接边，且未访问
            if (matrix[nodeIndex][j] == 1 && !isVisited(visitedMap, j)) {
                int nodeValue = nodes[j].value;

                visitor.visit(nodeValue);
                visitedMap.put(j, true);
                //递归搜索
                dfsReverse(visitor, visitedMap, j);
            }
        }
    }

    /**
     * 获取下一个未访问的邻接点
     * @param nodeIndex
     * @param visitedMap
     * @return
     */
    private int findNextUnvisitedNode(int nodeIndex, Map<Integer, Boolean> visitedMap) {
        for (int j = 0; j < nodeNum; j++) {
            if (matrix[nodeIndex][j] == 1 && !isVisited(visitedMap, j)) {
                return j;
            }
        }

        return -1;
    }

    /**
     * 获取所有未访问的邻接点
     * @param nodeIndex
     * @param visitedMap
     * @return
     */
    private List<Integer> findNextUnvisitedNodes(int nodeIndex, Map<Integer, Boolean> visitedMap) {
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < nodeNum; j++) {
            if (matrix[nodeIndex][j] == 1 && !isVisited(visitedMap, j)) {
                list.add(j);
            }
        }

        return list;
    }

    /**
     * 深度优先搜索  非递归算法
     * @param visitor
     */
    @Override
    public void dfsNonReverse(Visitor visitor) {
        if (nodeNum == 0) {
            return;
        }

        Stack<Integer> stack = new LinkedStack<>();
        Map<Integer, Boolean> visitedMap = new HashMap<>();
        int nodeIndex = 0;
        int value = nodes[nodeIndex].value;

        visitor.visit(value);
        visitedMap.put(nodeIndex, true);

        stack.push(nodeIndex);
        while (!stack.isEmpty()) {
            int nextNode = findNextUnvisitedNode(stack.peek(), visitedMap);
            if (nextNode == -1) {
                stack.pop();
            } else {
                int nextValue = nodes[nextNode].value;
                visitor.visit(nextValue);
                visitedMap.put(nextNode, true);

                stack.push(nextValue);
            }
        }
    }

    /**
     * 广度优先搜索
     * @param visitor
     */
    public void bfs(Visitor visitor) {
        if (nodeNum == 0) {
            return;
        }

        Queue<Integer> queue = new LinkedQueue<>();
        Map<Integer, Boolean> visitMap = new HashMap<>();

        int nodeIndex = 0;
        queue.enqueue(nodeIndex);

        while (!queue.isEmpty()) {
            int index = queue.dequeue();
            int value = nodes[index].value;
            visitor.visit(value);
            visitMap.put(index, true);

            List<Integer> list = findNextUnvisitedNodes(index, visitMap);
            if (list.size() > 0) {
                list.forEach(queue::enqueue);
            }
        }
    }

}
